题解 洛谷 P1045 [NOIP2003 普及组] 麦森数

简要题意：

给定一个数$p$，求$2^p$-1的位数和后500位的值，其中$p\in [1\times10^3,3.1\times10^6]$。

策略分析：

我们可以将这个问题分为两步来处理，第一步求出位数，第二步求后$500$位

求出位数：

首先有一个非常平凡的结论：$10^k$的位数为$k+1$。那么一个$10^k$的数的位数也等于$lg10^k$，设$n =2^p$，因为不存在最后一位为$0$的$2^p$的数，所以$2^p-1$的位数一定与$2^p$的位数相同。我们希望能够将$10^k$所具有的性质应用在$2^p$中，设$10^m=2$，那么$lg2=m$，所以$10^{lg2}=2$，所以$n=2^p=(10^{lg2})^p=10^{(lg2)·p}$，那么$n$的位数就等于$10^{(lg2)·p}$的位数，即$(lg2)·p+1$，那这不就简单多了，直接$cmath$库里随便一搞就出来了

求后500位的值：

我们发现一个朴素的高精度乘法的时间复杂度是$O(n^2)$，那么就寄了，所以我们要用超级快速的高精乘法，C++里什么样的数据类型存的数最大呢？（谁刚说__$int128$拉出去枪毙$5$分钟）显然我们要用$unsigned$ $long$ $long$来存储这500位，那么我们就要尽量挑战它的极限，一次乘$2^{60}$ （讨厌没有边界感的$ull$），这样我们就可以在更短的时间内完成计算

AC代码：

#include <iostream>
#include <cstdio>
#include <cmath>
#define ULL unsigned long long
using namespace std;

namespace Rick { int work() { cout << "Never gonna give you up, never gonna let you down~\n"; } }
namespace SHAWN {
    const int N = 507;
    ULL t[N] = { 1 };
    int p;
    int work()
    {
        cin >> p;
        cout << (int)(log10(2) * p) + 1 << '\n';
        for (; p > 0; p -= 60) {
            ULL jin = 0;
            for (int i = 0; i < 500; ++i) {
                if (p > 60) { t[i] <<= 60; }
                else { t[i] <<= p; }
                t[i] += jin; jin = t[i] / 10; t[i] %= 10;
            }
        }
        t[0] -= 1; 
        // 最开始为了让乘法有值我们设成了1，所以一通操作后要减1
        for (int i = 499; i >= 0; --i) {
            cout << t[i];
            if (! (i % 50)) { cout << '\n'; }
        }
        return 0;
    }
}

signed int main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    // return SHAWN :: work();
    return Rick :: work();
}